import java.util.*;

class Solution {

    // 错误解法：暴力枚举
    // public List<List<Integer>> threeSum(int[] nums) {
    //     List<List<Integer>> list = new ArrayList<>();
    //     // 1、先对数组整体排序
    //     Arrays.sort(nums);
    //     // 2、再去找符合条件的数据
    //     for (int i = 0; i <= nums.length-3; i++) {
    //         List<Integer> sub_list = new ArrayList<>();
    //         for (int j = i+1; j <= nums.length-2; j++) {
    //             for (int k = j+1; k <= nums.length-1; k++) {
    //                 // 这里可以优化一点点效率：>0的话，就直接跳出循环，
    //                 // 大于0，再继续往后走也没用(根本不可能出现==0的情况)
    //                 if (nums[i]+nums[j]+nums[k] == 0) {
    //                     sub_list.add(nums[i]);
    //                     sub_list.add(nums[j]);
    //                     sub_list.add(nums[k]);
    //                     List<Integer> integerList = new ArrayList<>(sub_list);
    //                     list.add(integerList);
    //                     sub_list.clear();
    //                 }
    //             }
    //         }
    //     }
    //     // 3、利用set对其去重
    //     Set<List<Integer>> set = new HashSet<>();
    //     // 遍历list将其中的元素插入set中
    //     for (int i = 0; i < list.size(); i++) {
    //         if (!set.contains(list.get(i))) {
    //             set.add(list.get(i));
    //         }
    //     }
    //     List<List<Integer>> new_list = new ArrayList<>();
    //     // 遍历set中的元素插入到new_
    //     for (List<Integer> x : set) {
    //         new_list.add(x);
    //     }
    //     return new_list;
    // }

    // // 正确解法：使用对撞指针降低时间复杂度
    // public List<List<Integer>> threeSum(int[] nums) {
    //     List<List<Integer>> list = new ArrayList<>();
    //     // 1、先对数组整体排序
    //     Arrays.sort(nums);
    //     // 2、再去找符合条件的数据
    //     for (int i = 0; i <= nums.length-3; i++) {
    //         List<Integer> sub_list = new ArrayList<>();
    //         int j = i+1;
    //         int k = nums.length-1;
    //         while (j < k) {
    //             if (nums[i]+nums[j]+nums[k] == 0) {
    //                     sub_list.add(nums[i]);
    //                     sub_list.add(nums[j]);
    //                     sub_list.add(nums[k]);
    //                     List<Integer> integerList = new ArrayList<>(sub_list);
    //                     list.add(integerList);
    //                     sub_list.clear();
    //                     // 只有一个增大，另一个减小，才可能达到相等
    //                     // 这里如果不是两个同时走的话，就会超出时间限制
    //                     j++;
    //                     k--;
    //             } else if (nums[i]+nums[j]+nums[k] > 0) {
    //                 // 得减小，k--
    //                 k--;
    //             } else { // < 0
    //                 // 得增加，j++
    //                 j++;
    //             }
    //         }
    //     }
    //     // 3、利用set对其去重
    //     Set<List<Integer>> set = new HashSet<>();
    //     // 遍历list将其中的元素插入set中
    //     for (int i = 0; i < list.size(); i++) {
    //         if (!set.contains(list.get(i))) {
    //             set.add(list.get(i));
    //         }
    //     }
    //     List<List<Integer>> new_list = new ArrayList<>();
    //     // 遍历set中的元素插入到new_list中
    //     for (List<Integer> x : set) {
    //         new_list.add(x);
    //     }
    //     return new_list;
    // }

    // 正确解法：对撞指针+查找去重
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        // 1、先对数组整体排序
        Arrays.sort(nums);
        // 2、再去找符合条件的数据
        for (int i = 0; i <= nums.length-3; i++) {
            // 与上一次的值相同，就不需要再进行重复的操作了
            while (i-1 >= 0 && i <= nums.length-3 && nums[i] == nums[i-1]) {
                i++;
            }
            // i对应的值一定是数组中最小的值，如果它都>0了，那肯定找不到了
            while (i < nums.length && nums[i] > 0) {
                i++;
            }
            List<Integer> sub_list = new ArrayList<>();
            int j = i+1;
            int k = nums.length-1;
            while (j < k) {
                if (nums[i]+nums[j]+nums[k] == 0) {
                    sub_list.add(nums[i]);
                    sub_list.add(nums[j]);
                    sub_list.add(nums[k]);
                    List<Integer> integerList = new ArrayList<>(sub_list);
                    list.add(integerList);
                    sub_list.clear();
                    // 只有一个增大，另一个减小，才可能达到相等
                    // 这里如果不是两个同时走的话，就会超出时间限制
                    j++;
                    k--;
                    // 如果和上一次的数据相同，则跳过
                    while (j < k && nums[j] == nums[j-1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k+1]) {
                        k--;
                    }
                } else if (nums[i]+nums[j]+nums[k] > 0) {
                    // 得减小，k--
                    k--;
                    // 数据与上一次相同的话，查找出来的还是同样的结果
                    while (j < k && nums[k] == nums[k+1]) {
                        k--;
                    }
                } else { // < 0
                    // 得增加，j++
                    j++;
                    // 数据与上一次相同的话，查找出来的还是同样的结果
                    while (j < k && nums[j] == nums[j-1]) {
                        j++;
                    }
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        // int[] nums = {-1,0,1,2,-1,-4};
        int[] nums = {-1,0,1,2,-1,-4,-2,-3,3,0,4};
        threeSum(nums);
    }
}